﻿using System;
using System.Collections.Generic;

public class TreeKD
{
    public Photon[] nodes;
    public TreeKD()
    {
    }
	public TreeKD(int capacity)
	{
        nodes = new Photon[capacity];
        for (int i = 0; i < capacity; i++)
            nodes[i] = new Photon();
	}
    public void createTree(List<Photon> map, int deep, int pos)
    {
        if (map.Count == 0)
        {
            return;// null;
        }
        int dim = deep % 3;
        Photon med = findMedian(map, dim);
        List<Photon> leftList = new List<Photon>();
        List<Photon> rightList = new List<Photon>();
        foreach (Photon p in map)
        {
            if (dim == 0)
            {
                if (p.position.x < med.position.x)
                    leftList.Add(p);
                else if (p.position.x > med.position.x)
                    rightList.Add(p);
            }
            else if (dim == 1)
            {
                if (p.position.y < med.position.y)
                    leftList.Add(p);
                else if (p.position.y > med.position.y)
                    rightList.Add(p);
            }
            else
            {
                if (p.position.z < med.position.z)
                    leftList.Add(p);
                else if (p.position.z > med.position.z)
                    rightList.Add(p);
            }
        }
        //NodeKD node = new NodeKD();
        //med.flag = dim;
        //NodeKD node = new NodeKD(med);
        //node.root = med;
        //node.root.flag = dim;
        //node.left = createTree(leftList, deep + 1, 2 * pos);
        //node.right = createTree(rightList, deep + 1, 2 * pos + 1);
        nodes[pos - 1] = med;
        createTree(leftList, deep + 1, 2 * pos);
        createTree(rightList, deep + 1, 2 * pos + 1);
        //return photon;
    }
    public Photon findMedian(List<Photon> map, int dim)
    {
        Photon ret;
        if (dim == 0)
            map.Sort(comparerX);
        else if (dim == 1)
            map.Sort(comparerY);
        else
            map.Sort(comparerZ);
        ret = map[map.Count / 2];
        ret.flag = dim;
        return ret;
    }
    public static int comparerX(Photon p1, Photon p2)
    {
        if (p1.position.x < p2.position.x)
            return -1;
        else if (p1.position.x == p2.position.x)
            return 0;
        else
            return 1;
    }
    public static int comparerY(Photon p1, Photon p2)
    {
        if (p1.position.y < p2.position.y)
            return -1;
        else if (p1.position.y == p2.position.y)
            return 0;
        else
            return 1;
    }
    public static int comparerZ(Photon p1, Photon p2)
    {
        if (p1.position.z < p2.position.z)
            return -1;
        else if (p1.position.z == p2.position.z)
            return 0;
        else
            return 1;
    }
}
